#include "linklist.h"

void AddToTail(LinkList* a, LinkList b) {
    if (!*a) {
        *a = b;
        return;
    }
    if (!b) {
        return;
    }
    LinkList p = *a;
    while (p->next) {
        p = p->next;
    }
    p->next = b;
}

int Length(LinkList L) {
    int length = 0;
    LinkList p = L->next; // 从链表的第一个节点开始
    while (p != NULL) {
        length++;
        p = p->next;
    }
    return length;
}
LinkList Search_First_Common(LinkList L1, LinkList L2) {
    int len1 = Length(L1), len2 = Length(L2);
    LinkList longList, shortList; // 分别指向较长和较短的链表
    int L; // 表长之差
    if (len1 > len2) {
        longList = L1->next;
        shortList = L2->next;
        L = len1 - len2;
    } else {
        longList = L2->next;
        shortList = L1->next;
        L = len2 - len1;
    }
    while (L--) {
        longList = longList->next;
    }
    while (longList != NULL) {
        if (longList == shortList) // 同步后移寻找共同结点
            return longList;
        else {
            longList = longList->next;
            shortList = shortList->next;
        }
    }
    return NULL;
}

int main() {
    char a[] = "load";
    char b[] = "be";
    char c[] = "hello";
    char d[] = "ing";

    LinkList la = CreateList(a);
    LinkList lb = CreateList(b);
    LinkList lc = CreateList(c);
    LinkList ld = CreateList(d);

    // 测试1
    LinkList r1 = Search_First_Common(la, lb);
    printf("测试1: \n");
    PrintList(la);
    PrintList(lb);
    PrintList(r1);

    // 测试2
    LinkList r2 = Search_First_Common(lb, lc);
    printf("测试2: \n");
    PrintList(lb);
    PrintList(lc);
    PrintList(r2);

    AddToTail(&la, ld);
    PrintList(la);
    AddToTail(&lb, ld);
    PrintList(lb);

    // 测试3
    LinkList r3 = Search_First_Common(la, lb);
    printf("测试3: \n");
    PrintList(la);
    PrintList(lb);
    PrintList(r3);

    // 测试4
    LinkList r4 = Search_First_Common(lb, lc);
    printf("测试4: \n");
    PrintList(lb);
    PrintList(lc);
    PrintList(r4);

    return 0;
}